{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Tree Vertical Order Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #hash-table #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #哈希表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: verticalOrder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的垂直遍历"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二叉树的根结点，返回其结点按 <strong>垂直方向</strong>（从上到下，逐列）遍历的结果。</p>\n",
    "\n",
    "<p>如果两个结点在同一行和列，那么顺序则为&nbsp;<strong>从左到右</strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/28/vtree1.jpg\" style=\"width: 282px; height: 301px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,9,20,null,null,15,7]\n",
    "<strong>输出：</strong>[[9],[3,15],[20],[7]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/28/vtree2-1.jpg\" style=\"width: 462px; height: 222px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,9,8,4,0,1,7]\n",
    "<strong>输出：</strong>[[4],[9],[3,0,1],[8],[7]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/28/vtree2.jpg\" style=\"width: 462px; height: 302px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,9,8,4,0,1,7,null,null,null,2,5]\n",
    "<strong>输出：</strong>[[4],[9,5],[3,0,1],[8,2],[7]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中结点的数目在范围 <code>[0, 100]</code> 内</li>\n",
    "\t<li><code>-100 &lt;= Node.val &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-tree-vertical-order-traversal](https://leetcode.cn/problems/binary-tree-vertical-order-traversal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-tree-vertical-order-traversal](https://leetcode.cn/problems/binary-tree-vertical-order-traversal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,9,20,null,null,15,7]', '[3,9,8,4,0,1,7]', '[3,9,8,4,0,1,7,null,null,null,2,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        columnTable = defaultdict(list)\n",
    "        queue = deque([(root, 0)])\n",
    "        while queue:\n",
    "            node, column = queue.popleft()\n",
    "            if node is not None:\n",
    "                columnTable[column].append(node.val)\n",
    "                queue.append((node.left, column - 1))\n",
    "                queue.append((node.right, column + 1))\n",
    "        return [columnTable[x] for x in sorted(columnTable.keys())]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def verticalOrder(self, root: 'TreeNode') -> 'List[List[int]]':\n",
    "        res = []\n",
    "        if root is None:\n",
    "            return res\n",
    "        \n",
    "        hmap = {}\n",
    "        q = []\n",
    "        cols = []\n",
    "        \n",
    "        q.append(root)\n",
    "        cols.append(0)\n",
    "        \n",
    "        m = 0\n",
    "        M = 0\n",
    "        \n",
    "        while(len(q)>0):\n",
    "            tmp = q.pop(0)\n",
    "            col = cols.pop(0)\n",
    "            \n",
    "            if col not in hmap:\n",
    "                hmap[col] = []\n",
    "                \n",
    "            hmap[col].append(tmp.val)\n",
    "            \n",
    "            if tmp.left is not None:\n",
    "                q.append(tmp.left)\n",
    "                cols.append(col-1)\n",
    "                m = min(m,col-1)\n",
    "                \n",
    "            if tmp.right is not None:\n",
    "                q.append(tmp.right)\n",
    "                cols.append(col+1)\n",
    "                M = max(M,col+1)\n",
    "            \n",
    "        for i in range(m,M+1):\n",
    "            res.append(hmap[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "    # def __init__(self, x):\n",
    "        # self.val = x\n",
    "        # self.left = None\n",
    "        # self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def verticalOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res = defaultdict(list)\n",
    "        d = deque()\n",
    "        d.append((root, 0))\n",
    "        while d:\n",
    "            node, level = d.popleft()\n",
    "            res[level].append(node.val)\n",
    "            if node.left:\n",
    "                d.append((node.left, level - 1))\n",
    "            if node.right:\n",
    "                d.append((node.right, level + 1))\n",
    "\n",
    "        return [res[x] for x in sorted(res.keys())]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "    # def __init__(self, x):\n",
    "        # self.val = x\n",
    "        # self.left = None\n",
    "        # self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def verticalOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res = defaultdict(list)\n",
    "        d = deque()\n",
    "        d.append((root, 0))\n",
    "        while d:\n",
    "            node, level = d.popleft()\n",
    "            res[level].append(node.val)\n",
    "            if node.left:\n",
    "                d.append((node.left, level - 1))\n",
    "            if node.right:\n",
    "                d.append((node.right, level + 1))\n",
    "\n",
    "        return [res[x] for x in sorted(res.keys())]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def verticalOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        from collections import deque,defaultdict\n",
    "        if not root: return []\n",
    "        queue=deque([(0,root)])\n",
    "        dic=defaultdict(list)\n",
    "        ans=[]\n",
    "        while queue:\n",
    "            idx,root=queue.pop()\n",
    "            dic[idx].append(root.val)\n",
    "            if root.left:\n",
    "                queue.appendleft( (idx-1,root.left) )\n",
    "            if root.right:\n",
    "                queue.appendleft( (idx+1,root.right) )\n",
    "        key=list(dic.keys())\n",
    "        key.sort()\n",
    "        \n",
    "        for k in key:\n",
    "            ans.append(dic[k])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def verticalOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        row = 0\n",
    "        if not root:\n",
    "            return []\n",
    "        s, m = float(\"inf\"), float(\"-inf\")\n",
    "        dp = [(root, row)]\n",
    "        ans = defaultdict(list)\n",
    "        while dp:\n",
    "            t, n = dp.pop(0)\n",
    "            if t:\n",
    "                s = min(s, n)\n",
    "                m = max(m, n)\n",
    "                ans[n].append(t.val)\n",
    "                dp.append((t.left, n-1))\n",
    "                dp.append((t.right, n+1))\n",
    "        t = []\n",
    "        for i in range(s, m+1):\n",
    "            if ans[i]:\n",
    "                t.append(ans[i])\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from collections import defaultdict, deque\n",
    "class Solution:\n",
    "    def verticalOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        rets, dict_ret = [], defaultdict(list)\n",
    "        if root is None:\n",
    "            return []\n",
    "        \n",
    "        q = deque()\n",
    "        q.append((root, 0))\n",
    "        while q:\n",
    "            cnt = len(q)\n",
    "            while cnt > 0:\n",
    "                cnt -= 1\n",
    "                node, level = q.popleft()\n",
    "                dict_ret[level].append(node.val)\n",
    "                if node.left:\n",
    "                    q.append((node.left, level-1))\n",
    "                if node.right:\n",
    "                    q.append((node.right, level+1))\n",
    "        \n",
    "        for ret in sorted(dict_ret):\n",
    "            rets.append(dict_ret[ret])\n",
    "        return rets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def verticalOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        min_level = max_level = 0\n",
    "        lst = collections.defaultdict(list)\n",
    "        res = []\n",
    "        queue = [(root, 0)]\n",
    "        while queue:\n",
    "            tem = []\n",
    "            for i in range(len(queue)):\n",
    "                node, level = queue[i]\n",
    "                if level not in lst:\n",
    "                    lst[level] = [node.val]\n",
    "                else:\n",
    "                    lst[level].append(node.val)\n",
    "                if node.left:\n",
    "                    min_level = min(min_level, level-1)\n",
    "                    tem.append((node.left, level-1))\n",
    "                if node.right:\n",
    "                    max_level = max(max_level, level+1)\n",
    "                    tem.append((node.right, level+1))\n",
    "            queue = tem\n",
    "        for i in range(min_level, max_level+1):\n",
    "            res.append(lst[i])\n",
    "        return res\n",
    "                \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def verticalOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "\n",
    "        hashmap = {}\n",
    "        q = [(root, 0)]\n",
    "        while q:\n",
    "            curr, vOrder = q.pop(0)\n",
    "\n",
    "            if vOrder not in hashmap:\n",
    "                hashmap[vOrder] = [curr.val]\n",
    "            else:\n",
    "                hashmap[vOrder].append(curr.val)\n",
    "\n",
    "            if curr.left:\n",
    "                q.append((curr.left, vOrder - 1))\n",
    "            if curr.right:\n",
    "                q.append((curr.right, vOrder + 1))\n",
    "        \n",
    "        ans = []\n",
    "        for key, value in sorted(hashmap.items()):\n",
    "            ans.append(value)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.min_idx = 0\n",
    "        self.max_idx = 0\n",
    "        self.ans = collections.deque([[]])\n",
    "\n",
    "    def verticalOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        self.dfs(root, 0, 0)\n",
    "\n",
    "        ans = []\n",
    "        for level in self.ans:\n",
    "            level.sort(key=lambda x: x[0])\n",
    "            ans.append([elem[1] for elem in level])\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def dfs(self, node, idx, h):\n",
    "        if node:\n",
    "            if idx < self.min_idx:\n",
    "                self.min_idx -= 1\n",
    "                self.ans.appendleft([])\n",
    "            elif idx > self.max_idx:\n",
    "                self.max_idx += 1\n",
    "                self.ans.append([])\n",
    "            actual_idx = idx - self.min_idx\n",
    "            self.ans[actual_idx].append((h, node.val))\n",
    "\n",
    "            self.dfs(node.left, idx - 1, h + 1)\n",
    "            self.dfs(node.right, idx + 1, h + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self._min = float('inf')\n",
    "        self._max = float('-inf')\n",
    "\n",
    "    def verticalOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "\n",
    "        res = []\n",
    "        self.helper(root, 0)\n",
    "\n",
    "        for _ in range(self._min, self._max+1):\n",
    "            res.append([])\n",
    "\n",
    "        queue = [(root, -self._min)]\n",
    "        while queue:\n",
    "            node, idx = queue.pop(0)\n",
    "            print('idx:', idx, 'min: ', self._min, 'max: ', self._max, 'node: ', node.val)\n",
    "            res[idx].append(node.val)\n",
    "            if node.left: queue.append((node.left, idx - 1))\n",
    "            if node.right: queue.append((node.right, idx + 1))\n",
    "            \n",
    "        return res\n",
    "\n",
    "    def helper(self, root, idx):\n",
    "        if not root: return\n",
    "        self._min = min(self._min, idx)\n",
    "        self._max = max(self._max, idx)\n",
    "        self.helper(root.left, idx - 1)\n",
    "        self.helper(root.right, idx + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def verticalOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:return []\n",
    "        d = collections.defaultdict(list)\n",
    "        queue = collections.deque([(root,0)])\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                node,col = queue.popleft()\n",
    "                d[col].append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append((node.left,col-1))\n",
    "                if node.right:\n",
    "                    queue.append((node.right,col+1))\n",
    "        ans = sorted(d.items())\n",
    "        return [v for k,v in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        ansls=collections.defaultdict(list)\n",
    "        if root==None:\n",
    "            return []\n",
    "        queue=collections.deque([[0,root]])\n",
    "        while queue:\n",
    "            size=len(queue)\n",
    "            for _ in range(size):\n",
    "                x=queue.popleft()\n",
    "                ansls[x[0]].append(x[1].val)\n",
    "                if x[1].left:\n",
    "                    queue.append([x[0]-1,x[1].left])\n",
    "                if x[1].right:\n",
    "                    queue.append([x[0]+1,x[1].right])\n",
    "        ls=sorted(ansls.items(),key=lambda x:x[0])\n",
    "        return [x[1] for x in ls]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res = []\n",
    "        if not root:\n",
    "            return res\n",
    "        node_order = {}\n",
    "        queue = [(root, 0)]\n",
    "        while queue:\n",
    "            new_queue = []\n",
    "            for node, order in queue:\n",
    "                if order in node_order:\n",
    "                    node_order[order].append(node.val)\n",
    "                else:\n",
    "                    node_order[order] = [node.val]\n",
    "                if node.left:\n",
    "                    new_queue.append((node.left, order-1))\n",
    "                if node.right:\n",
    "                    new_queue.append((node.right, order+1))\n",
    "            queue = new_queue\n",
    "        min_order = min(node_order.keys()) \n",
    "        max_order = max(node_order.keys())\n",
    "        for order in range(min_order, max_order+1):\n",
    "            res.append(node_order[order])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        minCol = maxCol = 0\n",
    "        traversal = collections.defaultdict(list)\n",
    "        queue = collections.deque([(root, 0)])\n",
    "        while queue:\n",
    "            node, col = queue.popleft()\n",
    "            minCol, maxCol = min(col, minCol), max(col, maxCol)\n",
    "            traversal[col].append(node.val)\n",
    "            if node.left:\n",
    "                queue.append((node.left, col - 1))\n",
    "            if node.right:\n",
    "                queue.append((node.right, col + 1))\n",
    "        return [traversal[col] for col in range(minCol, maxCol + 1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        ### solution\n",
    "        # DFS\n",
    "        # BFS\n",
    "\n",
    "        ## DFS\n",
    "        # pre order to ensure left and right for same cols\n",
    "        # sort cols by depth\n",
    "        def dfs(node,col,depth):\n",
    "            nonlocal cols\n",
    "            if not node: return\n",
    "            if node.left:\n",
    "                dfs(node.left,col-1,depth+1)\n",
    "            if node.right:\n",
    "                dfs(node.right,col+1,depth+1)\n",
    "            if col in cols: cols[col].append((node.val,depth))\n",
    "            else: cols[col] = [(node.val,depth)]\n",
    "            return\n",
    "\n",
    "        if not root: return []\n",
    "        cols = {}\n",
    "        dfs(root,0,0)\n",
    "        res = []\n",
    "        i,j = min(cols.keys()),max(cols.keys())\n",
    "        for col in range(i,j+1):\n",
    "            res.append([x[0] for x in sorted(cols[col],key=lambda t:t[1])])\n",
    "        return res\n",
    "\n",
    "        # BFS O(n) O(L)\n",
    "        # 1. use level order to ensure up->down\n",
    "        # 2. track col, save val to a map with col as key\n",
    "        if not root: return []\n",
    "        res = collections.defaultdict(list)\n",
    "        que = collections.deque([(root,0)])\n",
    "        while que:\n",
    "            n = len(que)\n",
    "            for _ in range(n):\n",
    "                p,col = que.popleft()\n",
    "                res[col].append(p.val)\n",
    "                if p.left: que.append((p.left,col-1))\n",
    "                if p.right: que.append((p.right,col+1))\n",
    "        i,j = min(res.keys()),max(res.keys())\n",
    "        return [res[col] for col in range(i,j+1)]\n",
    "\n",
    "        ## DFS\n",
    "        # pre order to ensure left and right for same cols\n",
    "        # sort cols by depth\n",
    "        def dfs(node,col,depth):\n",
    "            nonlocal cols\n",
    "            if not node: return\n",
    "            if col in cols: cols[col].append((node.val,depth))\n",
    "            else: cols[col] = [(node.val,depth)]\n",
    "            if node.left:\n",
    "                dfs(node.left,col-1,depth+1)\n",
    "            if node.right:\n",
    "                dfs(node.right,col+1,depth+1)\n",
    "            return\n",
    "\n",
    "        if not root: return []\n",
    "        cols = {}\n",
    "        dfs(root,0,0)\n",
    "        res = []\n",
    "        i,j = min(cols.keys()),max(cols.keys())\n",
    "        for col in range(i,j+1):\n",
    "            res.append([x[0] for x in sorted(cols[col],key=lambda t:t[1])])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from sortedcontainers import SortedDict\n",
    "from bisect import insort\n",
    "class Solution:\n",
    "    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        level = SortedDict()\n",
    "        def dfs(node, loc, depth):\n",
    "            if not node:\n",
    "                return\n",
    "            if loc not in level:\n",
    "                level[loc] = []\n",
    "            level[loc].append((depth, node.val))\n",
    "            dfs(node.left, loc - 1, depth + 1)\n",
    "            dfs(node.right, loc + 1, depth + 1)\n",
    "        dfs(root, 0, 0)\n",
    "        return  [[val for _, val in sorted(lst, key = lambda x: x[0])] for lst in level.values()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        que=[(root,0)]\n",
    "        dt=dict()\n",
    "        \n",
    "        while(que):\n",
    "            p,i=que.pop(0)\n",
    "            if i in dt:\n",
    "                dt[i].append(p.val)\n",
    "            else:\n",
    "                dt[i]=[p.val]\n",
    "            if p.left:\n",
    "                que.append((p.left,i-1))\n",
    "            if p.right:\n",
    "                que.append((p.right,i+1))\n",
    "        keys=dt.keys()\n",
    "        ans=[]\n",
    "        keys=sorted(keys)\n",
    "        for key in keys:\n",
    "            ans.append(dt[key])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        columns = collections.defaultdict(list)\n",
    "        # BFS\n",
    "        todo = collections.deque([(root, 0)])\n",
    "        while todo:\n",
    "            node, col = todo.popleft()\n",
    "            columns[col].append(node.val)\n",
    "            if node.left:\n",
    "                todo.append((node.left, col - 1))\n",
    "            if node.right:\n",
    "                todo.append((node.right, col + 1))\n",
    "\n",
    "        return [columns[i] for i in sorted(columns.keys())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        dic = collections.defaultdict(list)\n",
    "        level = [[root, 0]]\n",
    "        res = []\n",
    "\n",
    "        while level:\n",
    "            nxtLevel = []\n",
    "            for node, col in level:\n",
    "                dic[col].append(node.val)\n",
    "                if node.left:\n",
    "                    nxtLevel.append([node.left, col - 1])\n",
    "                if node.right:\n",
    "                    nxtLevel.append([node.right, col + 1])\n",
    "            level = nxtLevel\n",
    "        \n",
    "        minCol, maxCol = min(dic.keys()), max(dic.keys())\n",
    "        for i in range(minCol, maxCol + 1):\n",
    "            res.append(dic[i])\n",
    "        \n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
